#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;

template<class T>
class Less
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};

template<class T>
class Greater
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x > y;
	}
};

template<class T, class container, class compare = Less<T>>
class priority_que
{
public:
	void Adjustup(int child)
	{
		compare com;
		int parent = (child - 1) / 2;
		while (child > 0)
		{
			if (com(_con[parent], _con[child]))
			{
				swap(_con[parent], _con[child]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
				break;
		}
	}

	void Adjustdown(int parent)
	{
		compare com;
		int child = parent * 2 + 1;
		int n=size();
		while (child < n)
		{
			if (child + 1 < n && com(_con[child], _con[child + 1]))
			{
				++child;
			}
			if (com(_con[parent], _con[child]))
			{
				swap(_con[parent], _con[child]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
				break;
		}
	}

	void push(const T& x)
	{
		_con.push_back(x);
		Adjustup(_con.size() - 1);
	}

	void pop()
	{
		swap(_con[0], _con[_con.size() - 1]);
		_con.pop_back();
		Adjustdown(0);
	}

	const T& top()const
	{
		return _con[0];
	}

	bool empty()const
	{
		return _con.empty();
	}

	size_t size()const
	{
		return _con.size();
	}
private:
	container _con;
};
